Multicast transmission consists of sending a same content in the form of packets directed towards multiple recipients simultaneously. Multicast transmission provides important savings in terms of overhead for media distribution, such as for example internet television applications. Multimedia content may be offered for a fee, in which case the content may be encrypted prior to its distribution. Paying subscribers may receive encryption keys for use in decoding multicast content. Because end-users may subscribe to receive a content for a specific period of time, it is necessary to ensure backward and forward content secrecy.
Backward secrecy (BS) is a concept whereby, when a new user is authorized to join a multicast group, he should not be able to decrypt data previously transmitted to that multicast group. For example, if a new user subscribes to a new TV channel, although a multicast flow for this channel may have reached that new user before he subscribed, he should not be able to watch any previously stored data from that channel. Forward secrecy (FS) is a concept whereby, when the user gets revoked from a multicast group, although a multicast flow for that multicast group may continue reaching that user after the revocation, he should not be able to decrypt data received after the revocation. For example, a user can unsubscribe from a TV channel and should therefore be unauthorized (in a timely fashion) from watching it.
Logical Key Hierarchy (LKH) is a statefull rekeying algorithm requiring a key recovery algorithm to provide necessary keys to new users of a multicast group. The key recovery algorithm also allows providing keys to users having missed a rekeying message. LKH uses key encryption keys (KEK), which are keys for encrypting other keys. The concept of using KEKs is based on the fact that LKH uses keys to encrypt a content distributed through the hierarchy. When a new key is generated and is meant to replace a previous key, the new key is distributed encrypted by the previous key acting as a KEK. A logical hierarchical tree is built with a root key and a KEK for each additional level of the hierarchy. When a LKH tree is initially built, time invariant keys of each client node of the tree are initially used as KEKs for distributing, in unicast messages, encryption keys for use in decoding a multicast content. Thereafter, when the encryption keys are updated, a first distributed encryption key may be used as a KEK for distributing a next distributed encryption key. This ensures that no client node may detect a key at any time without first having obtained a first key through legitimate means.
FIGS. 1a, 1b and 1c, collectively referred to as FIG. 1, provide a prior art illustration of how LKH handles events in which users join or leave a binary LKH tree 100. FIG. 1a shows an initial LKH tree 100. The exemplary tree 100 is binary because each pair of client nodes 1101-7 at the bottom of the tree 100 is connected to an intermediate node 1201-3, each pair of intermediate node 1201-3 being connected to one more, higher layer node 1301-2, until a group key server 140 is found, at least from a logical standpoint, at the top of the hierarchy. The intermediate nodes 1201-3 and the higher layer nodes 1301-2 may consist of physical nodes or may alternatively exist only as logical nodes, for example as logical entities implemented within the group key server 140. Because there is an uneven number of client nodes 110 in the exemplary tree 100, client node 1107 may be actually directly connected to higher layer node 1302. Another manner of implementing the initial LKH tree 100 may be to connect the client node 1107 to an intermediate node 1204 (shown in FIG. 1b) even though there is in that case only that one client node 1107 connected the intermediate node 1204. The following description of FIG. 1 assumes, for illustration purposes, that the intermediate node 1204 is absent from the initial LKH tree 100 of FIG. 1a. This illustration is not meant to limit the scope of the background art addressed herein. It should also be noted that LKH trees are not limited to binary trees. In a non-binary tree, more than 2 nodes of a given level may connect to a node at an immediately above layer.
Message sequences support a join event in FIG. 1b, and a leave event in FIG. 1c. In the present description of FIG. 1, expressions such as “Kn” and “Kn—m” represent keys. The expression “Ka(Kb)” means that Kb is being distributed, encrypted by use of Ka, wherein Ka acts as a KEK. For example, K1—7 is a root key of the group key server 140, and is known by all nodes in the initial binary LKH tree 100 of FIG. 1a. Nodes at a given hierarchical level also have keys, which are known by subordinate nodes. For example, higher layer node 1302, has key K5—7, known by client nodes 1105-7. When user 8 (1108) joins the tree 100 in FIG. 1b, the already existing client node 1107 and the new client node 1108 become connected through a new intermediate node 1204 because the exemplary LKH tree 100 is binary. The higher layer node 1302 is essentially unchanged, except for the fact that it requires generation of a new key because it now supports one more client node 1108. The indicia within each node at an intermediate or higher level of FIG. 1, for example “5—8” in higher layer node 1302, are merely used in the present description as a convenient manner of illustrating which range of client nodes are supported by that intermediate or higher level node. Of course, the group key server 140 supports all client nodes of the LKH tree 100 and thus shows “1—7” in FIG. 1a (supporting client nodes 1101-7), “1—8” in FIG. 1b (supporting client nodes 1101-8), and “1—8*” in FIG. 1c (supporting a non-continuous range of client nodes 1101-2 and 1104-8). The indicia shown within each node do not represent any key value.
When the client node 1108 joins the tree 100 in FIG. 1b, a new K1—8 is randomly generated at the group key server 140, for the group key server itself. K1—8 is sent in a multicast rekey message 150 to previously existing nodes of the tree 100, encrypted by a previously known KEK (K1—7). Because all previously existing nodes on the right hand side of FIG. 1 need to acquire a new key for the higher layer node 1302, a new K5—8 is also randomly generated at the group key server 140. K5—8 is sent in the multicast rekey message 150 to previously existing nodes of the tree 100, encrypted by a KEK (K5—7) that is previously known to the client nodes 1105—7. The content of the multicast rekey message 150 is thus expressed as “K1—7(K1—8), K5—7(K5—8)”. It may be noted that nodes on the left hand side of the tree 100 do not possess the K5—7 and may simply ignore the K5—7(K5—8) component of the multicast rekey message 150.
If the intermediate node 1204 was not initially present and is now added to the tree 100, a new K78 is generated therefor at the group key server 140. K7—8 is sent in a unicast rekey message 152 to the client node 1107, encrypted with K7, which a shared key known by the client node 1107 and by the group key server 140. The content of the unicast rekey message 152 is thus “K7(K7—8)”.
K1—8, K5—8 and K7—8 are also sent in a unicast rekey message 154 to the new node 1108, using K8, which a shared key known by the new node 1108 and by the group key server 140. The content of the unicast rekey message 154 is thus “K8(K1—8, K5—8, K7—8)”.
FIG. 1c depicts the departure of a user of the client node 1103. The departure does not necessarily mean that the client node 1103 has physically left the tree 100, but rather that he is now unsubscribed and is no longer allowed to receive any content from the tree 100. As a result of this departure, the hierarchy underneath the group key server 140 and the higher layer node 1301 may have changed, the client node 1104 being now possibly connected directly to the higher layer node 1301. Of course, another option (not shown) may involve the intermediate node 1202 remaining in the tree 100, with 1104 remaining as the sole client node connected thereto. A new K1—8* and a new K1—4* are randomly generated by the group key server 140. The K1—8* and the K1—4* are distributed to all remaining nodes of the tree 100 by use of a multicast rekey message 156, with the exception of the node 1104 that receives a unicast rekey message 158. The client node 1104 receives the new K1—8* and the new K1—4* directed by the unicast rekey message 158, encrypted with K4, which a shared key known by the client node 1104 and by the group key server 140. The content of the unicast rekey message 158 is thus expressed as “K4(K1—8*, K1—4*)”. The content of the multicast rekey message 156 is “K5—8(K1—8*), K1—2(K1—8*, K1—4*)”. It should be noted that none of the messages of FIG. 1c is decryptable by the departed node 1103, even though that node might still be sniffing packets transmitted in the tree 100. This is because all rekey messages are encrypted by keys unknown to node 1103.
While FIG. 1 shows that key generation may be event-based, for example when a new user joins or when an existing user leaves, key regeneration may also be time-based, in a process commonly known as periodic batch rekeying.
The LKH architecture has some inherent deficiencies in that errors in the reception of a rekey message at a client node may render this client node incapable of decoding incoming multicast content. This deficiency is especially apparent when the architecture is used in wireless networks because such networks are prone to frequent transmission errors. As an example, the client node 1105 of FIG. 1 is a satellite TV decoder. Because of some weather condition, the client node 1105 may miss receiving the multicast rekey message 150 of FIG. 1b, which was sent when the client node 1108 had joined the tree 100. As a result, 1105 does not have the keys K5—8 and K1—8 and is therefore unable to decrypt later content encrypted with the group key K1—8. The algorithm for LKH does have a key recovery mechanism. However, while this mechanism effectively resends the necessary keys for an authorized client node having missed a rekey message, upon request from that client node, this mechanism is slow and adds delays to receiving subscribed content by the client node.